package com.gxc.string;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * 76. 最小覆盖子串

 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
 * 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 *
 * 注意：
 * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 */
public class MinWindow {

    public static void main(String[] args) {
        String s = "abcde";
        System.out.println(s.substring(0,5));
        System.out.println(s.substring(1,5));
        System.out.println(s.substring(4,5));
        System.out.println("==================");

        System.out.println(handle("ADOBECODEBANC", "ABC"));
        System.out.println(handle("a", "a"));
        System.out.println(handle("a", "aa"));
    }

    /**
     * 滑动窗口
     * 双指针
     * @param s
     * @param t
     * @return
     */
    public static String handle(String s, String t) {
        //目标的字符
        Map<Character, java.lang.Integer> ori = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            ori.put(c, ori.getOrDefault(c, 0)+1);
        }

        //当前的滑动窗口
        Map<Character, java.lang.Integer> cur = new HashMap<>();

        int l = 0, r = 0;
        int min = java.lang.Integer.MAX_VALUE, minL = -1, minR = -1;
        int sl = s.length();
        while (r<sl) {
            char c = s.charAt(r);
            if (ori.containsKey(c)) {
                cur.put(c, cur.getOrDefault(c, 0)+1);
            }

            //窗口右侧不动，窗口左侧缩小
            while (satisfy(ori, cur) && l <= r) {
                if (r + 1 - l < min) {
                    min = r +1 -l;
                    minL = l;
                    minR = r+1;
                }
                //窗口左侧缩小，左侧字符移出窗口

                char ch = s.charAt(l);
                if (ori.containsKey(ch)) cur.put(ch, cur.get(ch) - 1);
                l++;
            }
            r++;
        }
        //涵盖 t 所有字符的字符串
        return minL == -1 ? "": s.substring(minL, minR);
    }

    private static boolean satisfy(Map<Character,java.lang.Integer> ori, Map<Character,java.lang.Integer> cur) {
        Iterator<Map.Entry<Character, java.lang.Integer>> iterator = ori.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Character, java.lang.Integer> next = iterator.next();
            Character c = next.getKey();
            if (cur.getOrDefault(c, 0) < next.getValue()) return false;
        }
        return true;
    }

    class Solution {
        Map<Character, java.lang.Integer> ori = new HashMap<Character, java.lang.Integer>();
        Map<Character, java.lang.Integer> cnt = new HashMap<Character, java.lang.Integer>();

        public String minWindow(String s, String t) {
            int tLen = t.length();
            for (int i = 0; i < tLen; i++) {
                char c = t.charAt(i);
                ori.put(c, ori.getOrDefault(c, 0) + 1);
            }
            int l = 0, r = -1;
            int len = java.lang.Integer.MAX_VALUE, ansL = -1, ansR = -1;
            int sLen = s.length();
            while (r < sLen) {
                ++r;
                if (r < sLen && ori.containsKey(s.charAt(r))) {
                    cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
                }
                while (check() && l <= r) {
                    if (r - l + 1 < len) {
                        len = r - l + 1;
                        ansL = l;
                        ansR = l + len;
                    }
                    if (ori.containsKey(s.charAt(l))) {
                        cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
                    }
                    ++l;
                }
            }
            return ansL == -1 ? "" : s.substring(ansL, ansR);
        }

        public boolean check() {
            Iterator iter = ori.entrySet().iterator();
            while (iter.hasNext()) {
                Map.Entry entry = (Map.Entry) iter.next();
                Character key = (Character) entry.getKey();
                java.lang.Integer val = (java.lang.Integer) entry.getValue();
                if (cnt.getOrDefault(key, 0) < val) {
                    return false;
                }
            }
            return true;
        }
    }

    /**
     * 用 less 标记窗口内字符数量是否相等
     */
    class Solution2 {
        public String minWindow(String S, String t) {
            char[] s = S.toCharArray();
            int m = s.length;
            int ansLeft = -1;
            int ansRight = m;
            int left = 0;
            int less = 0;
            int[] cntS = new int[128]; // s 子串字母的出现次数
            int[] cntT = new int[128]; // t 中字母的出现次数
            for (char c : t.toCharArray()) {
                if (cntT[c]++ == 0) {
                    less++; // 有 less 种字母的出现次数 < t 中的字母出现次数
                }
            }
            for (int right = 0; right < m; right++) { // 移动子串右端点
                char c = s[right]; // 右端点字母（移入子串）
                if (++cntS[c] == cntT[c]) {
                    less--; // c 的出现次数从 < 变成 >=
                }
                while (less == 0) { // 涵盖：所有字母的出现次数都是 >=
                    if (right - left < ansRight - ansLeft) { // 找到更短的子串
                        ansLeft = left; // 记录此时的左右端点
                        ansRight = right;
                    }
                    char x = s[left++]; // 左端点字母（移出子串）
                    if (cntS[x]-- == cntT[x]) {
                        less++; // x 的出现次数从 >= 变成 <
                    }
                }
            }
            return ansLeft < 0 ? "" : S.substring(ansLeft, ansRight + 1);
        }
    }

}
